logo头像

野渡's小小知识乐园

8.最长回文子串与最长公共子串问题

算法与数据结构 动态规划 字符串 技术 2019/06/13

字符串处理是常见的问题，其中又数最长回文字符串比较经典，这里总结一下。

题目链接：https://leetcode-cn.com/problems/longest-palindromic-substring/

1、题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

1
2
3
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2：

1
2
输入: "cbbd"
输出: "bb"

2、解法1：暴力求解

找你所有可能的子串，判断每一个字串是否为回文串。字串有n^2个，每一个字串都需要遍历一遍才能确定是否回文，故时间复杂度为：O( n^3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) 
    {    
        int len = s.length(),maxlen=1,start=0; 

        for(int i = 0; i < len; i++) 
        for(int j = i + 1; j < len; j++) 
        {
            int index1 = i,index2 = j;//子串的两端坐标
            while(index1 < index2 && s[index1] == s[index2])//依次进行匹配
            {
                index1++;
                index2--;
            }
            if(index1 >= index2 && j - i + 1 > maxlen) //当前子串是回文子串
            {
                maxlen = j - i + 1;
                start = i;
            }
        }
        return s.substr(start,maxlen);//提取子串
    }
};

int main()
{
    Solution solu;
    cout<<"result:"<<solu.longestPalindrome("abb")<<endl;
    cout<<"result:"<<solu.longestPalindrome("")<<endl;
    cout<<"result:"<<solu.longestPalindrome("oho")<<endl;
    cout<<"result:"<<solu.longestPalindrome("ohomm")<<endl;
}

3、解法2：利用最长公共字串求解

本题可以转换为求解两个字符串的最长公共字串，对于输入字符串str，求其反转字符串rstr，求其最长公共子串即可。所以时间复杂度为求最长公共子串的时间复杂度：O(n^2),空间复杂度为O(n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) 
    {
        if(s.length()<=1) return s;//大小为1的字符串必为回文串

        string rev=s,ret,temp;
        reverse(rev.begin(),rev.end());//翻转字符串
        if(rev==s) return s;
        int len=0;//存放回文子串的长度
        for(int i=0;i<s.length();i++)//查找s与rev的最长公共子串
        {
            temp="";//存放待验证子串
            for(int j=i;j<s.length();j++)
            {
                temp+=s[j];//提取子串，每次增加一个字符
                if(temp.length()<len)  continue;//子串的长度不够....
                else if(rev.find(temp)!=-1)//在rev中找到temp
                {
                    string q=temp;//q用来验证temp是否是回文子串
                    reverse(q.begin(),q.end());
                    if(q==temp)
                    {
                        len=temp.length();
                        ret=temp;
                    }
                }
                else break;
            }
        }
        return ret;
    }
};

int main()
{
    Solution solu;
    cout<<"result:"<<solu.longestPalindrome("abbb")<<endl;
    cout<<"result:"<<solu.longestPalindrome("")<<endl;
    cout<<"result:"<<solu.longestPalindrome("ohomm")<<endl;
    cout<<"result:"<<solu.longestPalindrome("asdfghnmzxcv")<<endl;
}

关于如何求两个字符串的最长公共子串？一种比较合理的方式是分配一个二维数组，行和列分别对应的两个字符串的长度，对应的值表示两个字符串的字符是否相等。如果其i-1,j-1对应值大于0，则在其基础上+1。二位数组中的最大值即为最大长度。其实这也是一个动态规划问题，时间复杂度为O(n*m);

4、解法3：动态规划求解

定义dp[j][i]表示索引j到索引i的子串是否是回文串,为true时表示索引j到索引i形成的子串为回文子串，且子串起点索引为j,长度为i - j + 1。

我们知道，当只有一个字符时肯定是回文字符串，当有两个字符时，两个字符相等才能构成回文。那如果多个字符呢？其实可以递推，如果i到j回文，那么[i+1,j-1]也回文，反过来，要想[i,j]区间的字符串回文，那么str[i]需要等于str[j]并且[i+1，j-1]也回文。

对应的递推方程为：
image

实现代码为：(算法时间复杂度为O(N^2))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s) 
    {
        if(s.length()<=1) return s;//大小为1的字符串必为回文串
        
        bool dp[s.length()][s.length()];//用一个二维数组记录状态
        int maxlen = 1,start = 0; 
        memset(dp, 0, sizeof(dp)); //csting提供的函数
        
        for(int i = 0; i < s.length(); ++i)
        for(int j = 0; j <= i; ++j)
        {
            if(i - j < 2)  dp[j][i] = (s[i] == s[j]);
            else  dp[j][i] = (s[i] == s[j] && dp[j + 1][i - 1]);//递推

            if(dp[j][i] && maxlen < i - j + 1) //找到回文子串
            {
                maxlen = i - j + 1;
                start = j;
            }
        }
        return s.substr(start, maxlen);//提取子串
    }
};

int main()
{
    Solution solu;
    cout<<"result:"<<solu.longestPalindrome("abbb")<<endl;
    cout<<"result:"<<solu.longestPalindrome("")<<endl;
    cout<<"result:"<<solu.longestPalindrome("ohomm")<<endl;
    cout<<"result:"<<solu.longestPalindrome("asdfghnmzxcv")<<endl;
}

4、解法4：中心扩展法

中心扩展就是遍历字符串，以每一个字母为中心，向两边扩展，这样来找最长的子回文串。算法复杂度为O(N^2)。

需要考虑两种情况：

  • 长度为奇数的回文串，比如a, aba, abcba
  • 长度为偶数的回文串，比如aa, abba 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include <iostream>
#include <string>
using namespace std;

class Solution {
public:
    string longestPalindrome(string s)
    {
        if(s.length()<=1) return s;//大小为1的字符串必为回文串
        int len = s.size(),maxlen = 1,start = 0,j,k;

        for(int i = 0; i < len; i++)//求长度为奇数的回文串
        {
            j = i - 1, k = i + 1;//以i为中心点向两边展开
            while(j >= 0 && k < len && s[j] == s[k]) //相等，则得到一个回文串
            {
                if(k - j + 1 > maxlen)  maxlen = k - j + 1,start = j;
                j--,k++;//进一步扩展
            }
        }

        for(int i = 0; i < len; i++)//求长度为偶数的回文串
        {
            j = i, k = i + 1;
            while(j >= 0 && k < len && s[j] == s[k])
            {
                if(k - j + 1 > maxlen)  maxlen = k - j + 1,start = j;
                j--,k++;//进一步扩展
            }
        }
        return s.substr(start, maxlen);
    }
};

int main()
{
    Solution solu;
    cout<<"result:"<<solu.longestPalindrome("abbb")<<endl;
    cout<<"result:"<<solu.longestPalindrome("")<<endl;
    cout<<"result:"<<solu.longestPalindrome("ohomm")<<endl;
    cout<<"result:"<<solu.longestPalindrome("asdfghnmzxcv")<<endl;
}
转载声明：商业转载请联系作者获得授权,非商业转载请注明出处 © 野渡
访问量:   |   访客数:
Copyright © 2017 | Powered by Hexo | Theme by Snippet